package acm.pta3;

import 左哥算法.ch15并查集.UnionFindSet;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class T9 {
    public static void main(String[] args) throws IOException {
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        String[] read = in.readLine().split(" ");
        int n= Integer.parseInt(read[0]);
        int m= Integer.parseInt(read[1]);
        Graph graph = new Graph();
        while (m-- > 0) {
            read = in.readLine().split(" ");
            graph.add(Integer.parseInt(read[0]),Integer.parseInt(read[1]));
        }
        for (int i = 0; i < n; i++) {
            graph.nodes.putIfAbsent(i,new Node(i));
        }
        int[] capture=new int[Integer.parseInt(in.readLine())];
        read = in.readLine().split(" ");
        for (int i = 0; i < capture.length; i++) {
            capture[i]=Integer.parseInt(read[i]);
        }
//        dfsFun(graph,capture);
        unionFun(graph,capture);
    }
    /**
     * 思路1： dfs
     *      先构建一张图，将所有的边和点放入。captured
     *      准备一个set集合，存放被攻占的点，noPass
     *      1.得出块的个数
     *          准备一个Set集合，存放不能走的点
     *          对图中所有点尝试一次dfs，将走过的点放入到set集合中。
     *          查看需要进行几次dfs，得出块的个数。
     *
     *      2.之后每次攻占一个点，先将该点放入captured集合中，
     *          求一次块的个数，判断块是否比上一次多，如果增加则 报警
     */
    public static void dfsFun(Graph graph,int[] capture){
        Set<Node> captured=new HashSet<>();
        Collection<Node> values = graph.nodes.values();
        int preCount = cityCountDfs(values, new HashSet<>());
        for (int k : capture) {
            captured.add(graph.nodes.get(k));
            int count = cityCountDfs(values, new HashSet<>(captured)); //攻占之后的个数
            boolean isAlert=preCount<count;
            String res= (isAlert?"Red Alert: ":"")
                    +"City "+k+" is lost"
                    +(isAlert?"!":".");
            System.out.println(res);
            preCount=count;
        }
        if (capture.length>=values.size()){
            System.out.println("Game Over.");
        }
    }
    public static int cityCountDfs(Collection<Node> nodes, Set<Node> noPass){
        int count=0;
        for (Node node :nodes) {
            if (!noPass.contains(node)){
                dfsUnion(node,noPass);
                count++;
            }
        }
        return count;
    }
    public static void dfsUnion(Node node, Set<Node> set){
        set.add(node);
        for (Node next : node.nexts) {
            if (!set.contains(next)){
                dfsUnion(next,set);
            }
        }
    }


    /**
     * 思路2：并查集
     *      先构建一张图，将所有的边和点放入。
     *      准备一个set集合，存放被攻占的点，noPass
     *      1.得出块的个数
     *          将未被攻占的城市进行合并。
     *      2.之后每次攻占一个点，先将该点放入captured集合中，
     *          求一次块的个数，判断块是否比上一次多，如果增加则 报警
     */
    public static void unionFun(Graph graph,int[] capture){
        Set<Node> captured=new HashSet<>();
        Collection<Node> values = graph.nodes.values();
        int preCount = cityCountByUnion(values, captured);
        for (int k : capture) {
            captured.add(graph.nodes.get(k));
            int count = cityCountByUnion(values, captured);
            boolean isAlert=preCount<count;
            String res= (isAlert?"Red Alert: ":"")
                    +"City "+k+" is lost"
                    +(isAlert?"!":".");
            System.out.println(res);
            preCount=count;
        }
        if (capture.length>=values.size()){
            System.out.println("Game Over.");
        }
    }
    public static int cityCountByUnion(Collection<Node> nodes , Set<Node> noPass){
        UnionFindSet<Node> unionSet = new UnionFindSet<>();
        //todo 可以根据题目优化一个更加快速的并查集吗
        for (Node node : nodes) {
            if (!noPass.contains(node)){
                unionSet.init(node);
                for (Node next : node.nexts) {
                    if (noPass.contains(next))continue;
                    unionSet.union(node,next);
                }
            }
        }
        return unionSet.getSetCount();
    }


    static class Graph{
        Map<Integer,Node> nodes=new HashMap<>();

        public void add(Integer a,Integer b){
            Node A = nodes.getOrDefault(a, new Node(a));
            nodes.put(a,A);
            Node B = nodes.getOrDefault(b, new Node(b));
            nodes.put(b,B);
            A.nexts.add(B);
            B.nexts.add(A);
        }
    }
    static class Node{
        Integer val;
        Set<Node> nexts=new HashSet<>();

        public Node(Integer val) {
            this.val = val;
        }
    }
}
